package Q108

class Main {

}

fun main() {

}

class TreeNode2(var `val`: Int) {
    var left: TreeNode2? = null
    var right: TreeNode2? = null
}


/**
 * 将有序数组转换为二叉搜索树
 * @time 2022.4.25
 */
class Solution2 {
    fun sortedArrayToBST(nums: IntArray): TreeNode2? {
        return helper(0, nums.size - 1, nums)
    }

    //递归写法
    private fun helper(left: Int, right: Int, nums: IntArray): TreeNode2? {
        if (left > right) {
            return null
        }
        //这是二分查找计算中间值的新写法
        val mid = left + ((right - left) ushr 1)
        val res = TreeNode2(nums[mid])
        res.left = helper(left, mid - 1, nums)
        res.right = helper(mid + 1, right, nums)
        return res
    }
}
